package bite;

import java.util.Scanner;

/**
 * Creared with IntelliJ IDEA.
 * Description:标题：星际密码 | 时间限制：1秒 | 内存限制：32768K | 语言限制： 不限
 * 【星际密码】星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n
 * 对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
 * |1 1|^n => |Xn ..|
 * |1 0| |.. ..|
 * 例如n=2时，
 * |1 1|^2 => |1 1| * |1 1| => |2 1|
 * |1 0| |1 0| |1 0| |1 1|
 * 即2对应的数是“0002”。
 * User:yxd
 * Date:2022-05-21
 * Time:20:39
 */
public class Day25_1 {
    public static void main(String[] args) {
        //题就是矩阵的相乘,矩阵的第一行乘第一列相加和为第一个数,而按规律计算下来发现就是一个斐波那契数列的规律
        int[] nums = new int[10001];
        nums[1] = 1;
        nums[2] = 2;
        for (int i = 3; i < nums.length; i++) {
            nums[i] = (nums[i - 1] + nums[i - 2]) % 10000;
        }
        Scanner input = new Scanner(System.in);
        while (input.hasNext()){
            int n = input.nextInt();
            int[] arr = new int[n];
            for(int i = 0;i < n;i ++){
                arr[i] = input.nextInt();
            }
            StringBuilder stringBuilder = new StringBuilder();
            for(int i = 0;i < n;i ++){
                //按照04d的格式输出format:改变格式
                stringBuilder.append(String.format("%04d",nums[arr[i]]));
            }
            System.out.println(stringBuilder.toString());
        }
    }
}
